<HEAD>
  <SCRIPT SRC="../ganja.js"></SCRIPT>
</HEAD>
<BODY><SCRIPT>
// Create a Clifford Algebra with 2,0,1 metric.
Algebra(2,0,1,()=>{

  // in 2D, the seperating axis test involves testing overlap of the projection
  // onto one of the possible seperating axi. we support all regular ngons and
  // demonstrate intersection testing.

  // Some identities we'll use.
  var point      = (x,y)=>1e12-x*1e02+y*1e01,
      dist_pl    = (P,l)=>(P.Normalized^l.Normalized).e012,
      rotor      = (point,angle)=>Math.cos(angle/2) + Math.sin(angle/2)*point.Normalized,
      ngon       = (p,n,d,a)=>[...Array(n)].map((x,i)=>rotor(p,(a||0)+2*Math.PI*i/n)>>>(p+d*1e01));

  // the shapes can be moved around.
  var pa=point(0,0.2), pb=point(-0.8,1);
  
  var sat=(a,b)=>{
  // Collect potential axis candidates (all poly edges or half of them for symmetric polys)
    var e=[], da=[], db=[], i, al=a.length, bl=b.length;
    for (i=0; i<(al%2?al:al/2); i++) e[i]=a[i]&a[(i+1)%al];
    for (i=0; i<(bl%2?bl:bl/2); i++) e[i+al]=b[i]&b[(i+1)%bl];
  // Testing a single axis
    var check=(axis)=>{
      for (var i=0; i<al; i++) da[i]=dist_pl(a[i],axis);
      for (var i=0; i<bl; i++) db[i]=dist_pl(b[i],axis);
      return Math.min(...da)>Math.max(...db)||Math.min(...db)>Math.max(...da);
    }
  // Test all edges. Return the separating axis if found.
    for (i=0; i<e.length; i++) if (check(e[i])) return e[i];
  }
  
  document.body.appendChild(this.graph(()=>{
    // Animate point A
    pa[4] = 0.2-(0.3-(performance.now()*0.0001%2));

    // Create our polygons.
    var a=ngon(pa,3,0.65,pa.e01*10), b=ngon(pb,6,0.5);

    // Perform the SAT test.
    var h=sat(b,a);
    
    // Return the elements to display.
    return [
       0x224488, "Seperating Axis",                     // Title
       0x884488, h,                                     // Last axis
       h?0xB0FFD1:0xffB099, a, b,                       // ngons a,b
       0x448844, ...a.map((x,i,a)=>[x,a[i+1]||a[0]]),   // outline a
       0x448844, ...b.map((x,i,a)=>[x,a[i+1]||a[0]]),   // outline b
       0x224488, pa, pb                                 // center points
    ];   
  },{animate:true, lineWidth:3, labels:true, grid:true}));
  
});
</SCRIPT></BODY>